"""
https://leetcode.cn/problems/linked-list-cycle-ii/description/

142. 环形链表 II
已解答
中等
相关标签
premium lock icon
相关企业
给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

 

示例 1：



输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：



输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：



输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
 

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
 

进阶：你是否可以使用 O(1) 空间解决此题？

"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from typing import Optional
from list_node import ListNode,calc_arr,create_list_node


class Solution:
    """
    同样的龟兔赛跑思路可解，但需计算清楚。
    如果链表节点最后访问到None，则必定返回-1。
    否则链表节点分为两部分：前半部分直链，后半部分环形。
    环形部分指进行无数次遍历时，可被访问次数也是无数次的节点；与之相对的，仅能被访问一次的节点，被称为链表节点。
    同样是快慢节点追赶，当快节点追赶上慢节点时：
    1. 快节点的步数，是慢节点步数的2倍
    2. 两个节点必定都进入到了环形部分
    3. 两个节点相遇的位置，必定在慢节点走第一次环形部分的时候，此时快节点至少走完了一次环形部分

    假设直链长度为m,环形部分长度为n。目的是获取m
    m+f*n+x=2*(m+x)
    m+(f+2)*n+x=2*(m+n+x)
    f*n=m+x

    再上述公式中，n是可以比较容易求得的。只需在第一次相遇时，再各自走一圈，统计慢节点走的步数即可。
    获得n后，同时放出两个慢节点，但二者之间步数相差n。则两个慢节点第一次相遇时的地方，就是直链长度。
    

    """
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        root=ListNode(-1,head)
        slow=fast=root
        # 第一次循环
        has_cycle=False
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                has_cycle=True
                break
        if not has_cycle:
            return None
        
        # 获取n
        n=0
        while True:
            slow=slow.next
            fast=fast.next.next
            n+=1
            if slow==fast:
                break

        # 获取m
        slow1=slow2=root
        for i in range(n):
            slow2=slow2.next
        m=0
        while True:
            slow1=slow1.next
            slow2=slow2.next
            m+=1
            if slow1==slow2:
                break

        return slow1
    
if __name__=='__main__':
    node1=ListNode(1)
    node2=ListNode(2)
    node3=ListNode(3)
    node4=ListNode(4)
    node1.next=node2
    node2.next=node3
    node3.next=node4
    node4.next=node3

    sol=Solution()
    res=sol.detectCycle(node1)
    print(res.val)

    pass